Open In Colab

Formální síťová analýza¶

autor: Vojtěch Kaše (kase@ff.zcu.cz)

Úvod a cíle kapitoly¶

V tomto notebooku si budeme prakticky osvojovat koncepty síťové analýzy. Z veřejně dostupných dat si vytvoříme několik síťových grafů, které budeme dále upravovat, analyzovat a vizualizovat.

Jedním z nejhodnotnějších typů historických dat jsou sbírky dopisů, které nám umožňují sledovat kdo, s kým a kdy udřžoval kontakty. Řada těchto dopisních sbírek byla v posledních dekádách digitalizována. Existují tak například digitalizované kolekce sbírkek dopisů středověkých žen (https://epistolae.ctl.columbia.edu/letters/) nebo rozsáhlá kolekce raně novověkých dopisů EMLO (=Early Modern Letters Online, http://emlo-portal.bodleian.ox.ac.uk). Některé tyto datasety umožňují přístup pouze pomocí prohlížeče, a tudíž se nehodí pro datově analytickou práci. Jiné jsou naopak vzorovými příklady datového kurátorství. Ty zde budeme používat.

Konkrétně využijeme dataset dopisů mezi britskými vědci konce 18. a celého 19. století Ɛpsilon (web), vyvíjený týmem z Cambridge University Digital Library.

Ɛpsilon opens up new research opportunities in the history of 19th century science by bringing correspondence data and transcriptions from multiple sources into a single cross-searchable digital platform. It currently holds details of over 50,000 letters and is growing.

Alespoň z pohledu datové analýzy je velkou devízou tohoto projektu fakt, že veškerá data jsou dostupná nejen pro potřeby prohledávání a pročítání na webu projektu, ale také ve velice úhledné a praktické formě dostupná na GitHubu (zde). Nachází se zde jak digitální edice každého jednotlivého dopisu podle standardu TEI-XML, tak i tabulky metadat ve formátu CSV. S těmi budeme níže pracovat my, když se je přímo z GitHubu načteme do našeho výpočetního prostředí.

Nejprve budeme pracovat s kolekcí dopisů Londínské Linneovské společnosti, která byla založena roku 1788 a existuje dodnes (wikipedia). Ač nese jméno významného švédského vědce Carla Linného (wikipedia), otce vědecké taxonomie, tato vědecká společnost vznikla v Anglii až po jeho smrti.

Tabulková data budeme zpracovávat pomocí knihovny pandas. K síťové analýze využijeme knihovnu networkX, jejíž dokumentaci doporučuji k projití si - zde).

Cvičení 1: Korespondence Linnevské společnosti¶

Extrakce a přehled dat¶

In [1]:
import numpy as np
import pandas as pd
import requests
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import regex
In [2]:
# navštívíme url adresu, kde jsou umístěny všechny csv soubory
# načteme HTTP odpověď do JSON formátu (není možné vždy, ale zde to funguje
resp_json = requests.get("https://github.com/cambridge-collection/epsilon-data/tree/main/csv").json()

Nyní si vypíšeme obsah načtených dat a zorientujeme v příslušné struktuře:

In [3]:
resp_json

Vidíme, že ve struktuře je možné nalézt výpis jednotlivých csv souborů, které nás zajímají - nacházejí se pod tagem "tree", ten je však zanořen v dalších tagách.

In [4]:
resp_json["payload"]["tree"]["items"]
Out[4]:
[{'name': 'ampere.csv', 'path': 'csv/ampere.csv', 'contentType': 'file'},
 {'name': 'darwin-correspondence.csv',
  'path': 'csv/darwin-correspondence.csv',
  'contentType': 'file'},
 {'name': 'darwin-family-letters.csv',
  'path': 'csv/darwin-family-letters.csv',
  'contentType': 'file'},
 {'name': 'faraday.csv', 'path': 'csv/faraday.csv', 'contentType': 'file'},
 {'name': 'henslow.csv', 'path': 'csv/henslow.csv', 'contentType': 'file'},
 {'name': 'herschel.csv', 'path': 'csv/herschel.csv', 'contentType': 'file'},
 {'name': 'kemp.csv', 'path': 'csv/kemp.csv', 'contentType': 'file'},
 {'name': 'linnean-society.csv',
  'path': 'csv/linnean-society.csv',
  'contentType': 'file'},
 {'name': 'royal-society.csv',
  'path': 'csv/royal-society.csv',
  'contentType': 'file'},
 {'name': 'somerville.csv',
  'path': 'csv/somerville.csv',
  'contentType': 'file'},
 {'name': 'tyndall.csv', 'path': 'csv/tyndall.csv', 'contentType': 'file'}]
In [5]:
filenames = [item["name"] for item in resp_json["payload"]["tree"]["items"]]
filenames
Out[5]:
['ampere.csv',
 'darwin-correspondence.csv',
 'darwin-family-letters.csv',
 'faraday.csv',
 'henslow.csv',
 'herschel.csv',
 'kemp.csv',
 'linnean-society.csv',
 'royal-society.csv',
 'somerville.csv',
 'tyndall.csv']
In [6]:
linnean = pd.read_csv("https://raw.githubusercontent.com/cambridge-collection/epsilon-data/main/csv/linnean-society.csv")
linnean.head()
Out[6]:
id sender_surname sender_forename recipient_surname recipient_forename sorting_date date sender_address recipient_address source languages extent filename
0 LINNEAN1 Abbot Charles Smith Sir James Edward 1807-11-02 2 Nov 1807 Bedford, Bedfordshire NaN GB-110/JES/ADD/1, The Linnean Society of London eng NaN LINNEAN1.xml
1 LINNEAN2 Butt John Martin Smith Sir James Edward 1798-09-17 17 Sep 1798 Witley, Worcestershire NaN GB-110/JES/ADD/10, The Linnean Society of London eng NaN LINNEAN2.xml
2 LINNEAN3 Strutt Jacob George Smith Sir James Edward 1826-05-31 31 May 1826 London NaN GB-110/JES/ADD/100, The Linnean Society of London eng NaN LINNEAN3.xml
3 LINNEAN4 Swainson William Smith Sir James Edward 1815-04-22 22 Apr 1815 Palermo, Sicily London GB-110/JES/ADD/101, The Linnean Society of London eng NaN LINNEAN4.xml
4 LINNEAN5 Teesdale Robert Smith Sir James Edward 1789-11-18 18 Nov 1789 London London GB-110/JES/ADD/102, The Linnean Society of London eng NaN LINNEAN5.xml

Vidíme zde výpis prvních pěti řádek datové tabulky. Ale kolik vlastně tabulka čítá položek a kolik že je sloupců? To zjistíme z atributu shape (atributem je vlastnost datového objektu - jednou z vlastností datového objektu podle standardu pd.DataFrame je jeho tvar, tj. počet řádků a sloupců.

In [7]:
linnean.shape
Out[7]:
(3538, 13)

Než se pustíme do síťových analýz, ještě si upravíme hodnoty v některých sloupcích tak, aby se nám s nimi dobře pracovalo. Sloupec "sorting_date" vyjadřuje dataci daného dopisu ve velice úhledném a srozumitelném formátu (yyyy-mm-dd). Jelikož jsme však naše data načetl z prostého csv souboru, Python neví nic o tom, že za touto řadou čísel a pomlček se jedná o dataci; k tomu jej musíme nainstruovat.

V buňce níže za tímto účelem vytváříme nový sloupec s výmluvným názvem "datetime". Hodnoty v tomto sloupci jsou výsledkem použití (aplikování) funkce to_datetime() z knihovny pandas (pd) na hodnoty ve sloupci "sorting_date". Tato funkce "přeloží" jednotlivá čísla na roky, měsíce a dny.

In [8]:
linnean["datetime"] = linnean["sorting_date"].apply(pd.to_datetime)
linnean.head(5)
Out[8]:
id sender_surname sender_forename recipient_surname recipient_forename sorting_date date sender_address recipient_address source languages extent filename datetime
0 LINNEAN1 Abbot Charles Smith Sir James Edward 1807-11-02 2 Nov 1807 Bedford, Bedfordshire NaN GB-110/JES/ADD/1, The Linnean Society of London eng NaN LINNEAN1.xml 1807-11-02
1 LINNEAN2 Butt John Martin Smith Sir James Edward 1798-09-17 17 Sep 1798 Witley, Worcestershire NaN GB-110/JES/ADD/10, The Linnean Society of London eng NaN LINNEAN2.xml 1798-09-17
2 LINNEAN3 Strutt Jacob George Smith Sir James Edward 1826-05-31 31 May 1826 London NaN GB-110/JES/ADD/100, The Linnean Society of London eng NaN LINNEAN3.xml 1826-05-31
3 LINNEAN4 Swainson William Smith Sir James Edward 1815-04-22 22 Apr 1815 Palermo, Sicily London GB-110/JES/ADD/101, The Linnean Society of London eng NaN LINNEAN4.xml 1815-04-22
4 LINNEAN5 Teesdale Robert Smith Sir James Edward 1789-11-18 18 Nov 1789 London London GB-110/JES/ADD/102, The Linnean Society of London eng NaN LINNEAN5.xml 1789-11-18

Ač hodnoty ve sloupci "datetime" vypadají stejně jako hodnoty ve sloupci "sorting_date", chovají se odlišně. Umožňují nám přímo studovat časovou distribuci našich dat. Výhody tohoto formátu si všimneme, když na daný sloupec aplikujeme vizualizační metodu hist():

In [9]:
linnean["datetime"].hist()
Out[9]:
<Axes: >
No description has been provided for this image
In [10]:
linnean["18thcent?"] = linnean["datetime"] < pd.to_datetime("1801-01-01")
In [11]:
In [12]:
linnean["sender_agr"] = linnean.apply(lambda row: str(row["sender_surname"]).replace(" ", "_") + "_" + str(row["sender_forename"]).replace(" ", "_"), axis=1)

linnean["recipient_agr"] = linnean.apply(lambda row: str(row["recipient_surname"]).replace(" ", "_") + "_" + str(row["recipient_forename"]).replace(" ", "_"), axis=1)

Nyní se podíváme na osoby, který poslaly a přijaly největší množství dopisů:

In [13]:
linnean["sender_agr"].value_counts()
Out[13]:
sender_agr
Smith_Sir_James_Edward       481
Goodenough_Samuel            222
Woodward_Thomas_Jenkinson    101
Roscoe_William                98
Johnes_Thomas                 84
                            ... 
Erskine_David_Steuart          1
Upcher_Abbot                   1
Walcott_William                1
Baker_William_Lloyd            1
Cullen_Charles_Sinclair        1
Name: count, Length: 457, dtype: int64
In [14]:
linnean["recipient_agr"].value_counts()
Out[14]:
recipient_agr
Smith_Sir_James_Edward    2948
Macleay_Alexander          102
Smith_Pleasance             72
Roscoe_William              53
Unknown_nan                 51
                          ... 
Sutton_Charles               1
Brandreth_Mrs                1
Bright_Richard               1
Walker_George                1
Reeve_Robert                 1
Name: count, Length: 65, dtype: int64

V obou případech vidíme na prvním místě Sira Jamese Edwarda Smithe. Což, víme-li něco o Linneovské společnosti nebo podíváme-li se na wikipedii, není příliš překvapivé: jedná se o samotného zakladatele a dlouholetého předsedu této společnosti (viz wikipedia)).

V druhé tabulce vidíme na třetím místě také jeho manželku, Pleasance Smithovou, která byla taktéž významnou osobností dobového dění (taktéž viz wikipedie).

Tvorba síťových dat¶

Pro potřeby následujících si naše data výrazně přeskupíme a přetvoříme do podoby seznamu vážených vazeb.

In [15]:
linnean_edges = linnean.groupby(["sender_agr", "recipient_agr"]).size().reset_index()
linnean_edges.columns = ["sender_agr", "recipient_agr", "letters_n"]
linnean_edges.head()
Out[15]:
sender_agr recipient_agr letters_n
0 Abbot_Charles Smith_Sir_James_Edward 18
1 Acharius_Erik Smith_Sir_James_Edward 8
2 Acrel_Johan_Gustaf Smith_Sir_James_Edward 7
3 Afzelius_Adam Smith_Sir_James_Edward 14
4 Aiton_William_Townsend Smith_Sir_James_Edward 1

Jednotkou pozorování (čili řádkou tabulky) nyní již není každý jednotlivý dopis, ale pár odesilatele a příjemce s informací, kolik odesilatel příjemci zaslal dopisů (viz sloupec "letters_n"). Můžeme podívat na tabulku hran setříděnou od těch s největší váhou (tj. s nejvyšším počtem dopisů poslaných daným směrem).

In [16]:
linnean_edges.sort_values("letters_n", ascending=False)
Out[16]:
sender_agr recipient_agr letters_n
189 Goodenough_Samuel Smith_Sir_James_Edward 222
413 Smith_Sir_James_Edward Macleay_Alexander 102
525 Woodward_Thomas_Jenkinson Smith_Sir_James_Edward 101
348 Roscoe_William Smith_Sir_James_Edward 94
241 Johnes_Thomas Smith_Sir_James_Edward 83
... ... ... ...
352 Rous_Charlotte_Maria Smith_Sir_James_Edward 1
353 Rowden_Frances_Arabella Smith_Sir_James_Edward 1
158 Erskine_David_Steuart Smith_Sir_James_Edward 1
157 Engelhart_John_Henry Smith_Sir_James_Edward 1
533 Zimmermann_Eberhard_August_Wilhelm Smith_Sir_James_Edward 1

534 rows × 3 columns

In [17]:
In [18]:
G = nx.from_pandas_edgelist(linnean_edges, 'sender_agr', 'recipient_agr', 'letters_n', create_using=nx.DiGraph())
In [19]:
type(G)
Out[19]:
networkx.classes.digraph.DiGraph

Základní vlastnosti, které nás o našem grafu zajímají jsou, kolik má uzlů a kolik má hran?

In [20]:
G.number_of_nodes()
Out[20]:
476
In [21]:
G.number_of_edges()
Out[21]:
534

Další užitečnou informací je, kolik mají uzle v průměru vazeb (tzv. avarege degree).

In [22]:
sum(dict(G.degree).values()) / G.number_of_nodes()
Out[22]:
2.2436974789915967

Stejně tak zajímavé bude se podívat, který uzle mají nejvyšší in-degree (tj. vazeb do něj vstupujících) a out-degree (tj. vazeb z něj vystupujících). Podívejme se na deset uzlů s nejvyšší hodnotou in-degree:

In [23]:
sorted(dict(G.in_degree()).items(), key=lambda item: item[1], reverse=True)[:10]
Out[23]:
[('Smith_Sir_James_Edward', 445),
 ('Unknown_nan', 14),
 ('Smith_Pleasance', 6),
 ('Cullum_Sir_Thomas_Gery', 4),
 ('Lambert_Aylmer_Bourke', 2),
 ('Wallich_Nathaniel', 2),
 ('Goodenough_Samuel', 2),
 ('The_Linnean_Society_nan', 2),
 ('Banks_Sir_Joseph', 1),
 ('Barrington_Shute', 1)]

Vidíme, že zcela ústřední pozici zde zaujímá Sir James Edward Smith, zakladatel a dlouholetý předseda společnosti. Hned na druhém místě se v jednom uzlu potkávají dopisy, jejichž adresát je neznámý. Nebude od věci tento uzel ze sítě zcela odstranit.

In [24]:
G.remove_node("Unknown_nan")

Utvořený síťový graf si můžeme bezprostřdně vizualizovat pomocí funkce nx.draw():

In [25]:
nx.draw(G)
No description has been provided for this image

Bohužel vidíme, že výsledek vypadá spíše nevábně. Podle všeho se zde příliš mnoho uzlů poblíž středu. Vidíme, že vazby mají podobu šipek. Je tomu tak proto, že se jedná o tzv. směrový graf.

Abychom dosáhli lepších výsledků, přidáme do vizualizační funkce několik dodatečných parametrů

In [26]:
nx.draw(G, node_size=20, node_color="darkgreen", pos=nx.kamada_kawai_layout(G))
No description has been provided for this image

Uzly v grafu se jmenují stejně jako korespondenti. Pomocí syntaxe níže se tak můžeme podívat na vlastnosti jednotlivých vazeb.

In [27]:
G["Smith_Sir_James_Edward"]["Macleay_Alexander"]
Out[27]:
{'letters_n': 102}
In [28]:
G["Macleay_Alexander"]["Smith_Sir_James_Edward"]
Out[28]:
{'letters_n': 74}

Zde se dozvídáme, že zatímco Sir James Edward Smith poslal Alexanderu Macleayovi 102, v opačném směru jich šlo 74.

Pro některé typy analýz je praktičtější i smysluplnější pracovat s nesměrovým grafem. Vazba tak nezohledňuje směr příslušné korespondence a váha může odpovídat součtu vyměněných dopisů v obou směrech. Transformovat naši síť do této podoby vyžaduje několik řádek kódy, jimiž se zde nemusíme příliš zaobírat, důležitější je výsledek.

In [29]:
to_remove = []
edges_met = []
for node1, node2 in G.edges():
    if (G.has_edge(node2, node1)) & ((node2, node1) not in edges_met):
        G[node1][node2]["letters_n"] = G[node1][node2]["letters_n"] + G[node2][node1]["letters_n"]
        to_remove.append((node2, node1))
    edges_met.append((node1, node2))
In [30]:
len(edges_met)
Out[30]:
519
In [31]:
len(to_remove)
Out[31]:
35
In [32]:
for u,v in to_remove:
    G.remove_edge(u,v)
In [33]:
G = G.to_undirected().copy()
In [34]:
len(G.edges())
Out[34]:
484
In [35]:
G["Smith_Sir_James_Edward"]["Macleay_Alexander"]
Out[35]:
{'letters_n': 176}
In [36]:
G["Macleay_Alexander"]["Smith_Sir_James_Edward"]
Out[36]:
{'letters_n': 176}
In [37]:
weighted_degrees = {}
for node in G.nodes():
    weighted_degrees[node] = G.degree(node, weight='letters_n')
In [38]:
list(weighted_degrees.items())[:10]
Out[38]:
[('Abbot_Charles', 18),
 ('Smith_Sir_James_Edward', 3418),
 ('Acharius_Erik', 8),
 ('Acrel_Johan_Gustaf', 7),
 ('Afzelius_Adam', 14),
 ('Aiton_William_Townsend', 1),
 ('Allioni_Carlo', 7),
 ('Anderson_Alexander', 2),
 ('Anderson_James', 2),
 ('Anguish_Mrs_S', 1)]
In [39]:
# tento degree učiníme atributem našich uzlů
nx.set_node_attributes(G, weighted_degrees, 'weighted_degree')

Nyní si vyjmeme pouze uzly, které mají stupeň alespoň roven 2, tj. uzly osob, kteří v našem datasetu vedly korespondenci s více než jednou osobou.

In [40]:
node_list = [node for node in G.nodes if G.degree(node) >= 2]
len(node_list)
Out[40]:
28

Ukazuje se, že takových uzlů je v našem datasetu relativně málo. Vypišme si jejich jména.

In [41]:
node_list
Out[41]:
['Smith_Sir_James_Edward',
 'Barrington_Jane',
 'Lambert_Aylmer_Bourke',
 'Sutton_Charles',
 'Bicheno_James_Ebenezer',
 'Forster_Edward',
 'Boyd_George',
 'Roxburgh_William',
 'Brodie_James',
 'Coke_Thomas_William',
 'Wallich_Nathaniel',
 'Crowe_James',
 'Cullum_Sir_Thomas_Gery',
 'Smith_Pleasance',
 'Davy_Martin',
 'Don_George',
 'Goodenough_Samuel',
 'Drake_William_Fitt',
 'Gemmellaro_Carlo',
 'The_Linnean_Society_nan',
 'Gurney_Anna',
 'Harriman_John',
 'Johnes_Thomas',
 'Latham_John',
 'Martyn_Thomas',
 'Smith_James',
 'Swartz_Olof_Peter',
 'Webb_William']

Nyní tento seznam jmen využijeme k vymezení výseku z našeho grafu (nazveme si jej Gsub), který bude zahrnovat pouze tyto uzly.

In [42]:
Gsub = G.subgraph(node_list)
In [43]:
In [44]:
fig, ax = plt.subplots(1,1, figsize=(9, 6), dpi=300, tight_layout=True)

# pro potřeby vizualizace si ještě definujeme šířku čar jednotlivých vazeb,vycházející z objemu vyměněných dopisů. 
edge_widths = [np.sqrt(d['letters_n']) / 2 for (u, v, d) in Gsub.edges(data=True)]


nx.draw(Gsub, with_labels=True, pos=nx.kamada_kawai_layout(Gsub), node_size=100, nodelist=node_list, width=edge_widths, ax=ax)

ax.set_xlim(-1.3, 1.3)
Out[44]:
(-1.3, 1.3)
No description has been provided for this image

Z takovéto vizualizace již lze vypozorovat leccos.

Cvičení 2: Britská vědecká korespondence dlouhého 19. století jako celek¶

Extrace a předzpracování dat¶

Nyní se vrátíme na začátek. Projekt Ɛpsilon totiž hostí vícero kolekcí dopisů z podobného období a je na místě očekávat, že se osoby v těchto kolekcích budou alespoň částečně překrývat.

Vypišme si tedy nejprve jména csv souborů s metadaty k těmto kolekcím.

In [45]:
resp_json = requests.get("https://github.com/cambridge-collection/epsilon-data/tree/main/csv").json()
filenames = [item["name"] for item in resp_json["payload"]["tree"]["items"]]
filenames
Out[45]:
['ampere.csv',
 'darwin-correspondence.csv',
 'darwin-family-letters.csv',
 'faraday.csv',
 'henslow.csv',
 'herschel.csv',
 'kemp.csv',
 'linnean-society.csv',
 'royal-society.csv',
 'somerville.csv',
 'tyndall.csv']

Nyní pomocí cyklu FOR načteme data ze všech těchto souborů a nakonec je spojíme do jednoho objektu type pd.DataFrame.

In [46]:
dfs = [] # připrav prázdný seznam, který budeme následně postupně plnit daty z jednotlivých kolekcí 
for filename in filenames: # pro každý z našeho seznamu souborů:
    try: # zkus: jej načíst jako dataframe
        collection_df = pd.read_csv("https://raw.githubusercontent.com/cambridge-collection/epsilon-data/main/csv/" + filename)
        collection_df["source"] = filename # přidej tomuto dataframu nový sloupec "source", kde bude uvedeno jméno souboru, ze kterého pochází
        dfs.append(collection_df) # přidej do seznamu aktuální dataframe
    except: # pokud to nejde:
        print("failed: ", filename) # vypiš jméno souboru, u kterého to nejde
epsilon = pd.concat(dfs) # spoj do jednoho všechny dataframy uvnitř seznamu dfs

failed:  darwin-family-letters.csv
In [47]:
epsilon.head(5)
Out[47]:
id sender_surname sender_forename recipient_surname recipient_forename sorting_date date sender_address recipient_address source languages extent filename
0 L1 Ampère Jeanne-Antoinette (mère d'Ampère) Ampère André-Marie 1775-01-01 s.d. NaN NaN ampere.csv fra NaN L1.xml
1 L2 Maine de Biran Pierre Ampère André-Marie 1807-03-15 15 mars 1807 NaN NaN ampere.csv fra NaN L2.xml
2 L3 Ampère André-Marie Ampère Jean-Jacques (fils d'Ampère) 1775-01-01 s.d. NaN NaN ampere.csv fra NaN L3.xml
3 L4 Ampère André-Marie Duhamel Jean-Marie 1775-01-01 s.d. NaN NaN ampere.csv fra NaN L4.xml
4 L5 Ampère André-Marie Duhamel Jean-Marie 1775-01-01 s.d. NaN NaN ampere.csv fra NaN L5.xml
In [48]:
# jak dlouhý je náš dataset?
len(epsilon)
Out[48]:
47459
In [49]:
# stejně jako výše agregujme jména autorů a příjemců dopisů do podoby bez mezer a závorek
epsilon["sender_agr"] = epsilon.apply( lambda row: str(row["sender_surname"]).replace(" ", "_").partition(" (")[0] + "_" + str(row["sender_forename"]).replace(" ", "_").partition(" (")[0], axis=1)
epsilon["sender_agr"] = epsilon["sender_agr"].apply(lambda x: regex.sub("[^\p{L}_-]", "", x))

epsilon["recipient_agr"] = epsilon.apply( lambda row: str(row["recipient_surname"]).replace(" ", "_").partition(" (")[0] + "_" + str(row["recipient_forename"]).replace(" ", "_").partition(" (")[0], axis=1)
epsilon["recipient_agr"] = epsilon["recipient_agr"].apply(lambda x: regex.sub("[^\p{L}_-]", "", x))

Vypišme si nejplodnější autory a nejpopulárnější příjemce:

In [50]:
epsilon["sender_agr"].value_counts()
Out[50]:
sender_agr
Darwin_C_R             8151
Herschel_Sir_John      5353
Faraday_Michael        2985
Tyndall_John           1146
Airy_George_Biddell     751
                       ... 
Bunbury_E_H               1
Jacob_Edward              1
Smirke_E                  1
Copley_J_S                1
Bohn_Johann_C             1
Name: count, Length: 5763, dtype: int64
In [51]:
epsilon["recipient_agr"].value_counts()
Out[51]:
recipient_agr
Herschel_Sir_John                           9305
Darwin_C_R                                  6713
Smith_Sir_James_Edward                      2948
Faraday_Michael                             2102
Tyndall_John                                1291
                                            ... 
Humboldt_Friedrich_Wilhelm_Alexander_von       1
Plummer_Isabella_Erskine                       1
Magendie_François                              1
Ayres_Philip_Burnard                           1
Clausius_Adelheid                              1
Name: count, Length: 3945, dtype: int64

Tentokrát si data vazeb do nesměrové podoby převedeme ještě před vytvořením grafu.

In [52]:
epsilon_temp = epsilon.apply(lambda row: pd.Series(sorted([str(row["sender_agr"]), str(row["recipient_agr"])])), axis=1)
epsilon_temp.columns = ["node1", "node2"]
epsilon_edges = epsilon_temp.groupby(["node1", "node2"]).size().reset_index()
epsilon_edges.columns = ["node1", "node2", "weight"]
epsilon_edges = epsilon_edges[epsilon_edges["node1"] != epsilon_edges["node2"]]
epsilon_edges.head(5)
Out[52]:
node1 node2 weight
0 AB_Hewetson_nan Tristram_Henry_Baker 1
1 AB_nan Faraday_Michael 2
2 AT_TO_LOOK Unknown_nan 1
3 AW_Williamson_Foreign_Secretary_Royal_Society Williamson_Alexander_William 1
4 A_B Royal_Society_nan 1

Data v této podobě můžeme již neprodleně použít k tvorbě sítě váženého nesměrového grafu.

In [53]:
G = nx.from_pandas_edgelist(epsilon_edges, 'node1', 'node2', 'weight')

Opět se nejprve podíváme, z kolika uzlů a kolika hran naše síť sestává:

In [54]:
G.number_of_nodes()
Out[54]:
7646
In [55]:
G.number_of_edges()
Out[55]:
9088

Z těchto dat lze také snadno vypočítat tzv. average degree:

In [56]:
(2 * G.number_of_edges()) / G.number_of_nodes()
Out[56]:
2.377190687941407

U grafu s takto velkým počtem uzlů se nezřídka stane, že se ukáže, že je ve skutečnosti tvořen několika oddělenými komponenty, čili že síť není zcela propojená.

In [57]:
len(list(nx.connected_components(G)))
Out[57]:
166

Ano, to je i náš případ zde, když máme co dočinění s grafem, který sestává z více než 160 komponentů.

Podívejme se, z kolika uzlů sestává deset největších komponentů:

In [58]:
components_sorted = sorted(list(nx.connected_components(G)), key=len, reverse=True)
[len(comp) for comp in components_sorted][:10]
Out[58]:
[7295, 5, 4, 4, 3, 3, 3, 3, 3, 3]

Vidíme, že většina uzlů je součástí největšího komponentu, druhý největší komponent sestává již pouze z 5 uzlů. S klidným svědomím se nyní zaměříme pouze na největší komponent naší sítě.

In [59]:
len(components_sorted[0])
Out[59]:
7295
In [60]:
# Omezíme se na největší komponent.
G = G.subgraph(list(components_sorted[0]))
In [61]:
G.number_of_nodes() #zkontrolujeme, že se filtrace uzlů povedla
Out[61]:
7295

Pro potřeby několika dalších vizualizací nyní všem uzlům v rámci této sítě přiřadíme pozici v prostoru na základě jejich strukturelního postavení. Přiřazení těchto pozic v případě sítě, která sestává z tisíců uzlů, může být výpočetně poměrně náročné a zabrat nějaký čas. Abychom se níže vyhnuli zbytečnému čekání, vypočteme si tyto pozice uzlů již zde a dále je budeme používat v několika vizualizacích po sobě.

In [62]:
%%time
pos = nx.spring_layout(G)

CPU times: user 51.8 s, sys: 122 ms, total: 51.9 s
Wall time: 52.6 s
In [63]:
fig, ax = plt.subplots(figsize=(9,6), dpi=300)
nx.draw(G, node_size=10, node_color="darkgreen", pos=pos, ax=ax)
No description has been provided for this image

Tato síť již možná má některé zajímavé topografické vlastnosti, které si zaslouží bližší analytické ohledání.

Metriky centrality¶

Jedna skupina populárních a užitečných algoritmů jsou tzv. metriky centrality uzlů či vazeb. Uveďme si dvě takové metriky s jejich anglickými názvy a krátkým vysvětlením nejznámnější s jejich anglickými názvy:

  • degree centrality: je definován počtem vazeb, které daný uzel má
  • closeness centrality: součet vzdáleností nejkratších cest potřebných k dosažení všech ostatních uzlů uvnitř sítě.
  • betweenness centrality (mezilehlost): Jak často se ten který uzel nachází na trase spojující nejkratší cestou jakékoli další uzly uvnitř sítě.
  • PageRank centrality: je určen mnohonásobně opakovanými náhodnými procházkami po síti. Velikost PageRank je určena množstvím návštěv daného uzlu při těchto procházkách. Tento algoritmus byl původně vyvinut vývojáři od společnosti pro určení důležitých webových stránek.

S degree centrality jsme již vlastně pracovali, když jsme se u předchozí sítě omezili pouze na uzly s degree alespoň 2. Tato metrika je také nejsnáze srozumitelná a bude zajímavé si zde představit její výsledky pro potřeby srovnání s výsledky ostatních metrik. Jelikož zde však pracujeme s relativně rozsáhlou sítí a náš společný čas je omezený, vyzkoušíme si nyní pouze algrotimus pro PageRank, který je výpočetně nejméně náročný.

In [64]:
degree_centrality = nx.degree_centrality(G)
degree_top_nodes = sorted(degree_centrality.items(), key=lambda x:x[1], reverse=True)
degree_top_nodes[:10]
Out[64]:
[('Darwin_C_R', 0.27337537702221004),
 ('Herschel_Sir_John', 0.24362489717576088),
 ('Faraday_Michael', 0.1616397038661914),
 ('Smith_Sir_James_Edward', 0.06292843432958596),
 ('Tyndall_John', 0.0527831094049904),
 ('Henslow_J_S', 0.04154099259665478),
 ('Royal_Society_nan', 0.029064984919111598),
 ('nan_nan', 0.027282698108034),
 ('Ampère_André-Marie', 0.02604880723882643),
 ('Banks_Joseph', 0.01946805593638607)]
In [65]:
pagerank_centrality = nx.pagerank(G, max_iter=10000)
pagerank_top_nodes = sorted(pagerank_centrality.items(), key=lambda x:x[1], reverse=True)
pagerank_top_nodes[:10]
Out[65]:
[('Darwin_C_R', 0.12531743230350081),
 ('Herschel_Sir_John', 0.11578752463912399),
 ('Faraday_Michael', 0.057520944520063226),
 ('Smith_Sir_James_Edward', 0.028529193763289443),
 ('Tyndall_John', 0.022548106020346178),
 ('Henslow_J_S', 0.01330130754811916),
 ('Ampère_André-Marie', 0.011978899884381007),
 ('Hooker_J_D', 0.010425398525256518),
 ('Royal_Society_nan', 0.009683475973305872),
 ('nan_nan', 0.009509369237027814)]
In [66]:
%%time
betweenness_centrality = nx.betweenness_centrality(G)
betweenness_top_nodes = sorted(betweenness_centrality.items(), key=lambda x:x[1], reverse=True)
betweenness_top_nodes[:10]

CPU times: user 3min 1s, sys: 935 ms, total: 3min 2s
Wall time: 3min 8s
Out[66]:
[('Darwin_C_R', 0.4609313877075591),
 ('Herschel_Sir_John', 0.3988460586117793),
 ('Faraday_Michael', 0.30407842842289146),
 ('Smith_Sir_James_Edward', 0.1125311165691395),
 ('nan_nan', 0.09766682496924398),
 ('Tyndall_John', 0.09335990395332099),
 ('Royal_Society_nan', 0.07192907238232374),
 ('Henslow_J_S', 0.0656112688904613),
 ('Ampère_André-Marie', 0.04860372542234724),
 ('Banks_Joseph', 0.048231610499014956)]
In [67]:
degree_pagerank_comparison = []
for deg, page, betw in zip(degree_top_nodes, pagerank_top_nodes, betweenness_top_nodes):
    degree_pagerank_comparison.append([deg[0], page[0], betw[0]])
centr_comparison_df = pd.DataFrame(degree_pagerank_comparison)
centr_comparison_df.columns = ["degree_node", "pagerank_node", "betw_node"]
print(centr_comparison_df.head(20).round(2))

                 degree_node             pagerank_node               betw_node
0                 Darwin_C_R                Darwin_C_R              Darwin_C_R
1          Herschel_Sir_John         Herschel_Sir_John       Herschel_Sir_John
2            Faraday_Michael           Faraday_Michael         Faraday_Michael
3     Smith_Sir_James_Edward    Smith_Sir_James_Edward  Smith_Sir_James_Edward
4               Tyndall_John              Tyndall_John                 nan_nan
5                Henslow_J_S               Henslow_J_S            Tyndall_John
6          Royal_Society_nan        Ampère_André-Marie       Royal_Society_nan
7                    nan_nan                Hooker_J_D             Henslow_J_S
8         Ampère_André-Marie         Royal_Society_nan      Ampère_André-Marie
9               Banks_Joseph                   nan_nan            Banks_Joseph
10           Somerville_Mary       Airy_George_Biddell          Watson_William
11             Folkes_Martin              Banks_Joseph         Somerville_Mary
12         Mortimer_Cromwell             Sabine_Edward           Sabine_Edward
13              Birch_Thomas           Somerville_Mary           Folkes_Martin
14             Wedgwood_Emma           Babbage_Charles           Lyell_Charles
15  Herschel_Margaret_Brodie         Mortimer_Cromwell       Mortimer_Cromwell
16              Pringle_John  Herschel_Margaret_Brodie          Galton_Francis
17           Maskelyne_Nevil       Hirst_Thomas_Archer           Phillips_John
18             Sabine_Edward             Folkes_Martin            Lubbock_John
19             Parker_George        De_Morgan_Augustus            Birch_Thomas

V čem je toto srovnání potenciálně zajímavé? Podíváme-li se na pravou stranu tabulky, tj. uzly s největší betweenness centralitou, vidíme, že zejména ve druhé desítce se nachází nemálo uzlů, se kterými se na levé straně (u degree centrality) v první dvacítce vůbec nesetkáváme: Jinými slovy, jedná se o uzly, jejichž centralita v rámci sítě není živena výlučně množstvím vazeb, které uvnitř sítě mají, ale spíše specifickým strukturálním postavením. Podívejme se tedy na stejná data ještě jiným způsobem a totiž vypišme si, na kolikáté pozici se dvacítka uzlů s nejvyšší beteweenness centrality nachází z hlediska degree centrality.

In [68]:
for node in centr_comparison_df["betw_node"][:20]:
    print(node, " degree:", G.degree(node), "degree rank:", [el[0] + 1 for el in enumerate(degree_top_nodes) if el[1][0] == node][0], )
    

Darwin_C_R  degree: 1994 degree rank: 1
Herschel_Sir_John  degree: 1777 degree rank: 2
Faraday_Michael  degree: 1179 degree rank: 3
Smith_Sir_James_Edward  degree: 459 degree rank: 4
nan_nan  degree: 199 degree rank: 8
Tyndall_John  degree: 385 degree rank: 5
Royal_Society_nan  degree: 212 degree rank: 7
Henslow_J_S  degree: 303 degree rank: 6
Ampère_André-Marie  degree: 190 degree rank: 9
Banks_Joseph  degree: 142 degree rank: 10
Watson_William  degree: 39 degree rank: 21
Somerville_Mary  degree: 119 degree rank: 11
Sabine_Edward  degree: 41 degree rank: 19
Folkes_Martin  degree: 72 degree rank: 12
Lyell_Charles  degree: 19 degree rank: 39
Mortimer_Cromwell  degree: 68 degree rank: 13
Galton_Francis  degree: 12 degree rank: 66
Phillips_John  degree: 8 degree rank: 109
Lubbock_John  degree: 16 degree rank: 48
Birch_Thomas  degree: 66 degree rank: 14

Podívejme se nyní čtyři osobnosti:

  • Charles Lyell
  • Francis Galton
  • John Phillips
  • John Lubbock

Jejich degree rank je ve srovnání s jejich betweenness relativně vysoký. Zdá se, že tedy uzly mají v rámci grafu strukturálně zajímovou pozici.

Vytvořme tedy novou vizualizaci, v rámci které zaostříme pozornost právě na 20 uzlů s největší betweenness. Tyto uzly vyobrazíme odlišnou barvou a stejnou barvou vyobrazíme i jejich jména.

In [69]:
special_nodes = centr_comparison_df["betw_node"][:20] #["Lyell_Charles", "Galton_Francis", "Phillips_John", "Lubbock_John"]
special_pos = dict([(node, pos[node]) for node in special_nodes])
labels = {node: node for node in special_nodes}
In [70]:
fig, ax = plt.subplots(figsize=(24,18), dpi=300)
nx.draw(G, node_size=10, node_color="black", edge_color="grey",pos=pos, ax=ax, alpha=0.5)
nx.draw_networkx_nodes(G, nodelist=special_nodes, node_size=50, node_color="darkorange", pos=special_pos, ax=ax)
nx.draw_networkx_labels(G, font_color="darkorange", pos=special_pos, labels=labels,ax=ax)
Out[70]:
{'Darwin_C_R': Text(-0.24240782856941223, -0.1835523545742035, 'Darwin_C_R'),
 'Herschel_Sir_John': Text(-0.05920654907822609, 0.03125627711415291, 'Herschel_Sir_John'),
 'Faraday_Michael': Text(0.07666870206594467, -0.009823252446949482, 'Faraday_Michael'),
 'Smith_Sir_James_Edward': Text(0.2576848864555359, -0.1726907342672348, 'Smith_Sir_James_Edward'),
 'nan_nan': Text(0.23327383399009705, 0.29523658752441406, 'nan_nan'),
 'Tyndall_John': Text(0.007323220372200012, -0.1337890326976776, 'Tyndall_John'),
 'Royal_Society_nan': Text(0.2958509624004364, 0.3393012285232544, 'Royal_Society_nan'),
 'Henslow_J_S': Text(-0.20399868488311768, -0.05321016162633896, 'Henslow_J_S'),
 'Ampère_André-Marie': Text(0.08214311301708221, 0.233653724193573, 'Ampère_André-Marie'),
 'Banks_Joseph': Text(0.34255313873291016, 0.20324811339378357, 'Banks_Joseph'),
 'Watson_William': Text(0.3264940083026886, 0.26460760831832886, 'Watson_William'),
 'Somerville_Mary': Text(0.004037114791572094, -0.06527800112962723, 'Somerville_Mary'),
 'Sabine_Edward': Text(-0.021545175462961197, -0.006618051324039698, 'Sabine_Edward'),
 'Folkes_Martin': Text(0.3287908732891083, 0.48453035950660706, 'Folkes_Martin'),
 'Lyell_Charles': Text(-0.14943693578243256, -0.14990419149398804, 'Lyell_Charles'),
 'Mortimer_Cromwell': Text(0.44783398509025574, 0.5267356038093567, 'Mortimer_Cromwell'),
 'Galton_Francis': Text(-0.18355107307434082, -0.10792119801044464, 'Galton_Francis'),
 'Phillips_John': Text(-0.10157318413257599, -0.041374366730451584, 'Phillips_John'),
 'Lubbock_John': Text(-0.18244527280330658, -0.14187228679656982, 'Lubbock_John'),
 'Birch_Thomas': Text(0.43442702293395996, 0.44949376583099365, 'Birch_Thomas')}
No description has been provided for this image

Aby byl text čitelný a graf přehledný, vizualizace výše je výrazně větší než ty předchozí. Uložíme si ji do samostatného souboru ve formátu png.

In [71]:
try:
    fig.savefig("../figures/epsilon_betw.png") # pokud pracujeme s repozitoří jako celkem, včetně podlsožky "figures"
except:
    fig.savefig("epsilon_betw.png") # pokud pracujeme s notebookem samostatně, např. přes Google Colab

Detekce komunit¶

Další důležitou rodinou algoritmů jsou algoritmy pro detekování komunit, neboli shluků uzlů, které jsou mezi sebou provázány více, než z uzly z jejich okolí. Zde použijeme takzvanou Lovaňskou metodu (podle působiště výzkumníků, kteří ji vyvinuli [viz wikipedia]). Tento algoritmus se snaží nalézt takové rozdělení uzlů do komunit, které maximalizuje poměr vazeb mezi uzly uvnitř těchto komunit oproti jejich vazbám směrem ven z těchto komunit.

In [72]:
from networkx.algorithms import community
communities = nx.community.louvain_communities(G, seed=1)
len(communities)
Out[72]:
16

Algoritmus identifikoval 16 komunit. Podívejme se nejprve, kolik jednotlivé komunity čítají uzlů:

In [73]:
[len(com) for com in communities]
Out[73]:
[1104, 1081, 461, 184, 11, 259, 1989, 2, 3, 102, 332, 1692, 3, 2, 68, 2]
In [74]:
cmap = plt.get_cmap('viridis')
colors = [cmap(i) for i in np.linspace(0, 1, len(communities))]

fig, ax = plt.subplots(figsize=(24,18), dpi=300)
nx.draw_networkx_edges(G, edge_color="grey",pos=pos, alpha=0.5, ax=ax)

for community, color in zip(communities, colors):
    special_pos = dict([(node, pos[node]) for node in list(community)])
    #nx.draw(G, node_size=10, node_color="black", edge_color="grey",pos=pos, ax=ax, alpha=0.5)
    nx.draw_networkx_nodes(G, nodelist=list(community), node_size=10, node_color=[color], pos=special_pos, ax=ax)
ax.axis('off')
Out[74]:
(-0.7456697627902031,
 1.1317883536219597,
 -0.754230284690857,
 1.1666915655136108)
No description has been provided for this image

Vidíme, že tento algoritmus tedy dokáže velice pěkně zachytit strukturální vlastnosti dané sítě. To je v případě rozsáhlých grafů velice užitečné.

Alternativní datová sada: CorrespSearch¶

Alternativně bychom celé cvičení mohli absolvovat za využití mnoha dalších datasetů. Jedním z nich je dataset dostupný přes API na platformě CorrespSearch (web).

In [75]:
correspsearch = pd.read_csv("https://correspsearch.net/api/v2.0/csv.xql?", sep=";")
correspsearch.head(10)
Out[75]:
sender senderID senderPlace senderPlaceID senderDate addressee addresseeID addresseePlace addresseePlaceID addresseeDate edition key
0 Kf. Friedrich http://d-nb.info/gnd/11853579X NaN NaN NaN Universität Wittenberg http://d-nb.info/gnd/4032660-3 NaN NaN NaN Briefe und Akten zur Kirchenpolitik Friedrichs... 464
1 Alexius Crosner http://d-nb.info/gnd/128693517 Leipzig http://sws.geonames.org/2879139 1510 Julius Pflug http://d-nb.info/gnd/118714082 keine Angabe NaN NaN Julius Pflug. Correspondance, recueillie et éd... 1
2 Melanchthon http://d-nb.info/gnd/118580485 Tübingen http://sws.geonames.org/2820860 NaN Geraeander, Paul http://d-nb.info/gnd/1140261282 Tübingen http://sws.geonames.org/2820860 NaN Melanchthon Briefwechsel: Regesten online. Im ... 6a
3 Kf. Friedrich Hz. Johann http://d-nb.info/gnd/11853579X http://d-nb.inf... Torgau http://sws.geonames.org/2821807 1513-01-06 Bf. Johann III. von Naumburg http://d-nb.info/gnd/139152156 NaN NaN NaN Briefe und Akten zur Kirchenpolitik Friedrichs... 5
4 Räte Kf. Friedrichs NaN Torgau http://sws.geonames.org/2821807 1513-01-14 Bf. [Hieronymus] von Brandenburg http://d-nb.info/gnd/137650752 NaN NaN NaN Briefe und Akten zur Kirchenpolitik Friedrichs... 6
5 Bf. Hieronymus von Brandenburg http://d-nb.info/gnd/137650752 Ziesar http://sws.geonames.org/2804279 1513-01-24 Räte Kf. Friedrichs NaN NaN NaN NaN Briefe und Akten zur Kirchenpolitik Friedrichs... 7
6 Wolfgang Zesche Konvent des Augustinereremiten... http://d-nb.info/gnd/7754053-0 [Herzberg] http://sws.geonames.org/2905504 1513-01-30 Kf. Friedrich http://d-nb.info/gnd/11853579X NaN NaN NaN Briefe und Akten zur Kirchenpolitik Friedrichs... 8
7 Dekan [Eucharius Spiecker] Kapitel des Mariens... [Eisenach] http://sws.geonames.org/2931574 1513-02-01 Kf. Friedrich Hz. Johann http://d-nb.info/gnd/11853579X http://d-nb.inf... NaN NaN NaN Briefe und Akten zur Kirchenpolitik Friedrichs... 9
8 Kf. Friedrich Hz. Johann http://d-nb.info/gnd/11853579X http://d-nb.inf... Weimar http://sws.geonames.org/2812482 1513-03-06 Bf. Johann III. von Naumburg http://d-nb.info/gnd/139152156 NaN NaN NaN Briefe und Akten zur Kirchenpolitik Friedrichs... 13
9 Kf. Friedrich http://d-nb.info/gnd/11853579X Eilenburg http://sws.geonames.org/2931871 1513-03-16 Hz. Georg von Sachsen http://d-nb.info/gnd/118716921 NaN NaN NaN Briefe und Akten zur Kirchenpolitik Friedrichs... 14
In [76]:
%%time
for n in range(2,30):
    page_df = pd.read_csv("https://correspsearch.net/api/v2.0/csv.xql?x=" + str(n), sep=";")
    correspsearch = pd.concat([correspsearch, page_df])
    if n in range(0,3000,100):
        print(n)
    if len(page_df) < 100:
        break

CPU times: user 356 ms, sys: 58.7 ms, total: 414 ms
Wall time: 15.5 s
In [77]:
len(correspsearch)
Out[77]:
3036
In [78]:
correspsearch = correspsearch[correspsearch["sender"].notnull() & correspsearch["addressee"].notnull()]
len(correspsearch)
Out[78]:
2836